# -*- coding: utf-8 -*-            
# @Time : 2022/12/12 22:26
# @Author  : lining
# @FileName: 归并排序--优化.py
"""
问题：
在遍历完一个数组后即退出循环，退出后就要判断是那个数组还没遍历完，然后把剩下的数字添加进去
优化：
使用哨兵：把两个数字先拼接，在一起，给出1，2两个数组的索引，存放到两个新的列表中，然后再原列表中进行排序，当一个遍历完后，剩下的数字就是有序的
"""
class MergeSort():
    def mergesort(self, list_a, list_b):
        """
        :param list_a: 有序数组a
        :param list_b: 有序数组b
        :return:
        """
        i = 0
        j = 0
        z = 0
        list_new = list_a+list_b
        # 两个数组都要增加哨兵，避免越界
        list_a.append(9999)
        list_b.append(9999)
        while list_a[i]<9999:
            if list_a[i] >= list_b[j]:
                list_new[z] = list_b[j]
                j = j+1
            else:
                list_new[z] = list_a[i]
                i = i+1
            z = z+1
        print(list_new)


a = [1,2,3,4,5,11]
b = [2,6,7,8,9,10]
MergeSort().mergesort(a, b)
